1. Field of the Invention
The present invention generally relates to data compression/restoration methods, and more particularly to a method of encoding two-dimensional image data into compressed information by fast cosine transformation (FCT) and a method of decoding the compressed information by inverse fast cosine transformation (IFCT).
2. Related Art
Conventionally, several kinds of orthogonal transformation have been used in the field of digital signal processing. Among these kinds of the orthogonal transformation, the discrete cosine transformation (DCT) is widely used for speech signal processing and image data compression, because when discrete cosine transformation is used spectrum power concentrates primarily in a low frequency range. In general, a linear discrete cosine transformation (DCT) with respect to an input data including the number (N) of elements x(n) is defined as follows: ##EQU1## Because Formula (1) concerning a linear data contains a coefficient "2/N", the result of computing a two-dimensional DCT using the Formula (1) twice will have a coefficient "(2/N).sup.2 ". This number "N" of the elements of the input data is selected from among numbers equal to powers of 2. Therefore, the coefficient as a part of the formula can be calculated simply through a bit shifting.
A linear inverse discrete cosine transformation (IDCT) with respect to an input data including the number (N) of elements X(k) is defined as follows: ##EQU2##
The above described DCT and IDCT can be computed by repeatedly performing arithmetic operations of addition and multiplication. Generally, there are three major techniques for computing a discrete cosine transformation (DCT) of two-dimensional input data or computing an inverse discrete cosine transformation (IDCT):
a) performing polynomial calculations with respect to picture elements (pixels) in rows of input data, and, independently of the above polynomial calculations, performing polynomial calculations of picture elements in columns of the input data;
b) performing linear DCT/IDCT calculations of elements in rows of input data and independently performing linear DCT/IDCT calculations of elements in columns of the input data; and
c) perform two-dimensional DCT/IDCT calculations for each one block into which a matrix of the input data is divided.
The above method a) enables the computation of the two-dimensional DCT/IDCT by repeatedly performing additions and multiplications. This method is suitable for computations by means of digital signal processors (DSP) and the like. However, the above method a) is not adequate for carrying out high speed computation because it requires a great number of operations to be executed to complete the computation.
The above method c) can achieve the computation of the two-dimensional DCT/IDCT by performing a relatively small number of operations, but it must carry out a complicated procedure of computation and it is often very difficult to properly control the computation unit for computing the two-dimensional DCT/IDCT by the above method c). Therefore, there are presently no practical computation techniques or apparatus in which the method c) is implemented.
FIG. 6 of the parent patent application is a diagram for explaining the principle of the data compression/restoration to which the above method b) is applied. For carrying out a two-dimensional data compression, two-dimensional image input data is divided into prescribed blocks (for example, 8.times.8 pixel arrays). A first linear DCT circuit 31 shown in FIG. 6 calculates a linear discrete cosine transformation with respect to 8 pixels in rows of one 8.times.8 block into which the two-dimensional image data is divided, and the result of computing the linear discrete cosine transformation, or the output of the first linear DCT circuit 31, is stored in a transposition memory 32. Next, a second linear DCT circuit 33 reads out the data concerned from the transposition memory 32 and again independently computes a linear discrete cosine transformation with respect to the eight picture elements in columns of the 8.times.8 block. Then, two-dimensional data containing the information obtained through the linear DCT being twice repeated, is quantized by a quantization circuit 34. The resultant data is transmitted to a given unit on a receiving side or is recorded in a given storage medium.
Recently, international standardization efforts for developing a standard of data compression techniques for coding a natural static image data into compressed information are under way. A technique of computing a two-dimensional DCT technique by means of an 8.times.8 pixel data unit will certainly be chosen as the international standard. As described above, computation of the two-dimensional DCT can be realized by performing linear DCT calculations independently with respect to elements in rows and columns. However, for obtaining the two-dimensional DCT of two-dimensional data of one block having 8.times.8 picture elements in accordance with Formula (1) above, 1024 real number multiplications and 896 additions must be computed per block. Accordingly, for calculating the two-dimensional DCT with respect to information of one screen containing 512.times.512 picture elements, at least approximately 4.20 million (=1024.times.(512/8).times.(512/8)) real number multiplications must be executed. This calculation is quite time-consuming.
To achieve more rapid computation of this kind of arithmetic operations, Applicant has realized that a conventional fast cosine transformation (FCT) and inverse fast cosine transformation (IFCT) can be applied, and the linear DCT circuits 31, 33 of the parent patent application may be replaced by FCT circuits and the linear IDCT circuits 36, 38 may be replaced by IFCT circuits, respectively, as indicated by parentheses in FIG. 6.
In general, several algorithms for computing the FCT and the IFCT have been proposed. Among these algorithms, there are two conventional algorithms worthy of mention here. One is Chen's 8-element FCT and IFCT algorithms which are shown in FIGS. 1 and 2, respectively. The other is Wang's 8-element FCT and IFCT algorithms which are shown in FIGS. 4 and 5, respectively. In these drawings, a black circle denotes "add" operation and a white circle indicates no operation. Symbols placed along a straight line connecting one circle to another as indicated in these drawings, such as "Ck.pi.", "Sk.pi.", are an abbreviated symbol that indicates a trigonometric value used as a multiplication factor in a butterfly operation. For example, "Ck.pi." denotes the value of cos (k.pi.) and "Sk.pi." indicates the value of sin (k.pi.) . In a case of the Chen's algorithms shown in FIGS. 1 and 2, the computations of 8-element linear DCT and 8-element linear IDCT are each realized by sixteen (16) real number multiplications and twenty-six (26) additions. And, in a case of the Wang's algorithms shown in FIGS. 4 and 5, they are each realized by twenty (20) real number multiplications and twenty six (26) additions.
In addition, FIG. 3A shows a typical example of butterfly operation, and FIG. 3B shows a modified example of the butterfly operation. By applying this modified butterfly operation to the Chen's algorithms shown in FIGS. 1 and 2, it is possible to achieve the computation of the 8-element linear DCT or the 8-element linear IDCT by means of thirteen (13) real number multiplications and twenty nine (29) additions. Accordingly, the use of the modified butterfly operations will allow the computation of two-dimensional DCT and two-dimensional IDCT with respect to one block having 8.times.8 picture elements by means of 200 real number multiplications and 465 additions. When compared with the above described case in which simple multiplications and simple additions are used, the number of arithmetic operations required can be reduced to 1/5, thus allowing a faster computation for data compression and restoration to be carried out.
In order to increase the speed of computation, it is necessary to minimize the number of multiplications to be executed, because a "multiply" operation takes much greater computation time than that of an "add" operation. And, in order to achieve faster encoding of two-dimensional data or decoding of compressed information into the original two-dimensional data, it is desired to minimize the number of real number multiplications required for the linear FCT or the linear IFCT. However, conventional linear FCT and IFCT techniques do not provide sufficient computation speed and therefore require much computation time. There still is a need to improve the efficiency of use of computing devices in FCT and IFCT circuits.